class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> ret;
        if (!root) return ret;
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (q.size())
        {
            vector<int> tmp;
            int sz = q.size();
            while (sz--)
            {
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            if (i % 2 == 0) reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
            i++;
        }
        return ret;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        queue<Node*> q;
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            while (sz--)
            {
                Node* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                for (auto e : front->children) q.push(e);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};
class Solution {
public:
    string decodeString(string s)
    {
        stack<string> st1;
        stack<int> st2;
        st1.push("");
        for (int i = 0; i < s.size(); )
        {
            if (s[i] == '[')
            {
                i++;
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st1.push(tmp);
            }
            else if (s[i] == ']')
            {
                i++;
                string str = st1.top();
                st1.pop();
                int count = st2.top();
                st2.pop();
                while (count--) st1.top() += str;
            }
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + s[i] - '0';
                    i++;
                }
                st2.push(tmp);
            }
            else if (s[i] >= 'a' && s[i] <= 'z')
            {
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st1.top() += tmp;
            }
        }
        return st1.top();
    }
};
class Solution {
public:
    int calculate(string s)
    {
        char op = '+';
        stack<long long> st;
        for (int i = 0; i < s.size(); )
        {
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') op = s[i++];
            else if (s[i] >= '0' && s[i] <= '9')
            {
                long long tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + s[i] - '0';
                    i++;
                }
                if (op == '+') st.push(tmp);
                else if (op == '-') st.push(-tmp);
                else if (op == '*') st.top() *= tmp;
                else st.top() /= tmp;
            }
            else i++;
        }
        int ret = 0;
        while (!st.empty())
        {
            ret += st.top();
            st.pop();
        }
        return ret;
    }
};
class Solution {
public:
    string ChangeStr(string str)
    {
        string ret;
        for (auto e : str)
        {
            if (e != '#') ret += e;
            else
            {
                if (ret.size() > 0) ret.pop_back();
            }
        }
        return ret;
    }
    bool backspaceCompare(string s, string t)
    {
        return ChangeStr(s) == ChangeStr(t);
    }
};
class Solution {
public:
    string removeDuplicates(string s)
    {
        string ret;
        for (auto ch : s)
        {
            if (ret.size() == 0 || ret.back() != ch) ret += ch;
            else ret.pop_back();
        }
        return ret;
    }
};